package 贪心算法;

import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

public class 去除重复字母 {

    public static String removeDuplicateLetters(String s) {
        HashMap<Character, Integer> hashMap = new HashMap<>();
        int n = s.length();
        int k = 0;
        for (int i = 0; i < n; i++) {
            char key = s.charAt(i);
            if (hashMap.get(key)== null){
                hashMap.put(key,1);
            }else {
                k++;
                hashMap.put(key,hashMap.get(key)+1);
            }
        }
        HashSet<Character> hashSet = new HashSet<>();
        Deque<Character> stack = new LinkedList<>();
        stack.push(s.charAt(0));
        hashSet.add(s.charAt(0));
        for (int i = 1; i < n; i++) {
            char c = s.charAt(i);
            if (!hashSet.contains(c)){
                while (!stack.isEmpty() && c <stack.peek()&& hashMap.get(stack.peek()) > 1 & k>0){
                    Character pop = stack.pop();
                    hashMap.put(pop, hashMap.get(pop) - 1);
                    hashSet.remove(pop);
                    k--;
                }
                hashSet.add(c);
                stack.push(c);
            }else {
                hashMap.put(c,hashMap.get(c)-1);
                k--;
            }
        }
        StringBuffer sb = new StringBuffer();
        while (!stack.isEmpty()){
            sb.append(stack.pollLast());
        }
        return sb.toString();

    }

    public static void main(String[] args) {
        String s = "cbacdcbc";
        System.out.println(removeDuplicateLetters(s));
    }
}
